#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>
using namespace std;

// 城市类 - 表示一个城市信息
struct City {
    string name; // 名称（标识）
    struct Trip* head; // 从该城市出发的相邻路径(用链表存储)
    int amount = -1; // 从起点出发到该城市的总票价（总路径长度）
    City* prev; // 双向链表的前指针
    City* next; // 双向链表的后指针

    City(const string& name) : name(name), head(nullptr), prev(nullptr), next(nullptr) {}
};

// 航班类（表示一条路径）
struct Trip {
    City* start; // 航班起点
    City* end; // 航班终点
    int price; // 航班票价（边权重，或称路径长度）
    Trip* next; // 单指针 - 指向同一个起点的下一条邻边

    Trip(City* s, City* t, int p, Trip* n) : start(s), end(t), price(p), next(n) {}
};

class TripPlanSolution {
public:
    // 维护所有城市列表
    unordered_map<string, City*> cities;

    // 从列表获取城市，如果不在列表中则新建一个并添加
    City* getCity(const string& name) {
        if (cities.find(name) != cities.end()) {
            return cities[name];
        } else {
            City* c = new City(name);
            cities[name] = c;
            return c;
        }
    }

    // 添加航班（有向边）
    void addTrip(const string& start, const string& end, int price) {
        City* startCity = getCity(start);
        City* endCity = getCity(end);
        // 创建航班对象，并使用头插法把航班添加到起点城市的邻接表中
        Trip* trip = new Trip(startCity, endCity, price, startCity->head);
        startCity->head = trip;
    }

    // 用Dijkstra计算（不超预算的）所有航班路线
    unordered_map<string, int> findAllShortestPath(const string& src, int budget) {
        // 创建存放答案的容器
        unordered_map<string, int> answer;

        // 初始化起点信息：创建排序链表并将起点放入为第一个元素
        City* headCity = getCity(src);
        headCity->amount = 0;

        // 执行dijkstra搜索最短路径
        while (headCity != nullptr) {
            // 取出头节点作为当前节点，输出到答案
            City* s = headCity;
            headCity = headCity->next;
            answer[s->name] = s->amount;

            // 枚举当前城市的邻接路径，发现新的路径并更新维护排序数组
            for (Trip* trip = s->head; trip != nullptr; trip = trip->next) {
                // 当前路径的目标点为t，当前总路径长度=起点到s长度+s到t的长度
                City* t = trip->end;
                int newAmount = s->amount + trip->price;

                // 题目要求：不考虑超出预算的航线
                if (newAmount > budget) continue;

                // 情形1: 该相邻点第一次访问，使用插入排序加入队列
                if (t->amount == -1) {
                    // 计算当前搜索到的路径长度（权值）
                    t->amount = newAmount;
                    // 使用头插法插入排序将该顶点加入队列
                    if (headCity == nullptr || t->amount <= headCity->amount) {
                        if (headCity != nullptr) {
                            t->next = headCity;
                            headCity->prev = t;
                        }
                        headCity = t;
                    } else {
                        City* c = headCity;
                        while (c->next != nullptr && c->next->amount < t->amount)
                            c = c->next;
                        t->next = c->next;
                        if (c->next != nullptr) c->next->prev = t;
                        c->next = t;
                        t->prev = c;
                    }
                }
                // 情形2: t 之前被搜索到，且当前路径需要更新
                else if (newAmount < t->amount) {
                    // 更新旅途费用
                    t->amount = newAmount;

                    // 定位到新的排序位置
                    City* c = t;
                    while (c != headCity && c->prev->amount > t->amount)
                        c = c->prev;

                    // 执行链表位置交换
                    if (t != c) {
                        // 先将t从链表移除
                        t->prev->next = t->next;
                        if (t->next != nullptr) t->next->prev = t->prev;
                        // 再将t插入链表（替换c的位置）
                        if (c == headCity) {
                            headCity->prev = t;
                            t->next = headCity;
                            headCity = t;
                        } else {
                            t->prev = c->prev;
                            if (t->prev != nullptr)
                                t->prev->next = t;
                            t->next = c;
                            c->prev = t;
                        }
                    }
                }
            }
        }

        // 返回最终结果
        return answer;
    }
};

int main() {
    TripPlanSolution sln;
    sln.addTrip("广州", "长沙", 200);
    sln.addTrip("广州", "北京", 800);
    sln.addTrip("广州", "上海", 300);
    sln.addTrip("长沙", "武汉", 500);
    sln.addTrip("武汉", "北京", 100);
    sln.addTrip("上海", "武汉", 200);
    sln.addTrip("上海", "北京", 600);
    string src = "广州";
    int budget = 500;
    auto ms = sln.findAllShortestPath(src, budget);
    int n = ms.size();
    cout << "从" << src << "出发, 预算" << budget << "元, 共有以下" << n << "个方案:" << endl;
    for (const auto& pair : ms)
        cout << "到" << pair.first << ", 共" << pair.second << "元" << endl;
    return 0;
}